package com.cf.r952_ak;

import java.io.*;

public class f {

    public static int MAXN = 200001;
    public static int[] a = new int[MAXN];
    public static int[] c = new int[MAXN];
    public static int h, n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(System.out);
        in.nextToken();
        int T = (int) in.nval;
        while (T-- > 0) {
            in.nextToken(); h = (int) in.nval;
            in.nextToken(); n = (int) in.nval;

            for (int i = 0; i < n; i++) {
                in.nextToken(); a[i] = (int) in.nval;
            }
            for (int i = 0; i < n; i++) {
                in.nextToken(); c[i] = (int) in.nval;
            }
            long l = 1, r = (long) 1e12;
            while (l < r) {
                long m = l + ((r - l) >> 1);
                if (check(m)) r = m;
                else l = m + 1;
            }
            out.println(l);
        }

        out.flush();
        out.close();
        br.close();
    }

    public static boolean check(long x) {
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += (long) a[i] * ((x + c[i] - 1) / c[i]);
            if (sum >= h) return true;
        }
        return false;
    }
}
